import java.util.ArrayList;
import java.util.List;

/**
 * 123. 买卖股票的最佳时机 III
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 */
public class Solutions_123 {
    public static void main(String[] args) {
        int[] prices1 = {3, 3, 5, 0, 0, 3, 1, 4};  // output: 6
        int[] prices2 = {1, 2, 3, 4, 5};  // output: 4
        int[] prices3 = {7, 6, 4, 3, 1} ;  // output: 0
        int[] prices4 = {1};  // output: 0

        List<int[]> inputs = new ArrayList<>();
        inputs.add(prices1);
        inputs.add(prices2);
        inputs.add(prices3);
        inputs.add(prices4);

        for (int[] input : inputs) {
            int result = maxProfit(input);
            System.out.println(result);
        }
    }

    /**
     * 每天有且仅有 5 个状态，即不操作、第一次买、第一次卖、第二次买、第二次卖
     * 行：天数
     * 列：操作
     *      不操作   第一次买   第一次卖   第二次买  第二次卖
     * 3     0        -3        0        -3       0
     * 3     0        -3        0        -3       0
     * 5     0        -3        2        -3       2
     * 0     0        0         2         2       2
     * 0     0        0         2         2       2
     * 3     0        0         3         2       5
     * 1     0        0         3         2       5
     * 4     0        0         4         2       6
     *
     * - 当天若不操作，利润为 0，可以省略该步操作
     *
     * - 当天若是第一次买，所得利润为 0 - prices[i]，为什么是 0？因为之前没有卖出过，所以利润一定是 0
     *   但是还要比较更优，若当前买入后，所得利润还小于前一天买入后的利润，那么当天就不买
     *
     * - 当天若是第一次卖，所得利润为第一次买入的最优利润 + 当天的价格
     *   但是还要比较更优，若当前卖出后，所得利润还小于前一天卖出后的利润，那么当天就不卖
     *
     * - 当天若是第二次买，所得利润为第一次卖出后的最优利润 - 当天的价格
     *   但是还要比较更优，若当前买入后，所得利润还小于前一天买入后的利润，那么当天就不买
     *
     * - 当天若是第二次卖，所得利润为第二次买入的最优利润 + 当天的价格
     *   但是还要比较更优，若当前卖出后，所得利润还小于前一天卖出后的利润，那么当天就不卖
     */
    public static int maxProfit(int[] prices) {
        int days = prices.length;
        if (days < 2) {
            return 0;
        }
        int[][] dp = new int[days][4];
        // 设置初始值
        dp[0][0] = -prices[0];
        dp[0][2] = -prices[0];

        for (int i = 1; i < days; i++) {
            // 当天不操作
            // 当天为第 1 次买
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            // 当天为第 1 次卖
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            // 当天为第 2 次买
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            // 当天为第 2 次卖
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
        }
        return dp[days - 1][3];
    }
}
